package leetcode.biweekly.week86;

//Solution3Test
public class Solution3 {

	int[] nums;

	int m, n;

	public int maximumRows(int[][] mat, int cols) {
		m = mat.length;
		n = mat[0].length;
		nums = new int[m];
		for (int i = 0; i < m; i++) {
			int num = 0;
			for (int j = 0; j < n; j++) {
				int cur = mat[i][j];
				if (cur == 1) {
					num |= 1 << j;
				}
			}
			nums[i] = num;
		}
		int limit = 1 << n;
		Integer[][] dp = new Integer[n + 1][limit];
		return this.find(0, limit - 1, cols, dp);
	}

	private int find(int index, int limit, int cols, Integer[][] dp) {
		if (index == n) {
			int cnt = 0;
			for (int i = 0; i < m; i++) {
				if ((nums[i] & limit) == 0) {
					cnt++;
				}
			}
			return cnt;
		}
		if (dp[index][limit] != null) {
			return dp[index][limit];
		}
		int ans = 0;
		if (cols > 0) {
			ans = this.find(index + 1, limit ^ (1 << index), cols - 1, dp);
		}
		ans = Math.max(ans, this.find(index + 1, limit, cols, dp));
		dp[index][limit] = ans;
		return ans;
	}

}
